/*
 * @lc app=leetcode.cn id=343 lang=cpp
 *
 * [343] 整数拆分
 */

// @lc code=start
class Solution {
public:
    int integerBreak(int n) {
        //整数拆分 这道题其实我没有直接想到怎么解决
        //1.dp[i]表达i可以拆分相乘的最大数
        //2.初始化dp[2]=1 dp[3]=2 dp[4]=4
        //3.递归方程 dp[i]
        //没推出来递归方程 下面copy了
        //dp[i] = max({dp[i], (i - j) * j, dp[i - j] * j});
        vector<int> dp(n + 1);
        dp[2] = 1;
        for (int i = 3; i <= n; i++)
        {
            for (int j = 1; j < i - 1; j++)
            {
                dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
            }
        }
        return dp[n];
    }
};
// @lc code=end

